COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	Circumscription and philosophy
C00003 00003	%2∃z.(integer z ∧ ∀x.(integer x ⊃ x' ≠ z)) ∧ ∀x.(integer x ⊃ integer x')%1
C00005 00004	EPISTEMOLOGICAL PROBLEMS OF ARTIFICIAL INTELLIGENCE
C00011 00005	Heuristics of Circumscription
C00013 ENDMK
C⊗;
Circumscription and philosophy
 
I am hopeful that the concept of circumscription can be used to clarify

some philosophical problems.
%2∃z.(integer z ∧ ∀x.(integer x ⊃ x' ≠ z)) ∧ ∀x.(integer x ⊃ integer x')%1
 
circumscribes to
 
%2∃z.(qF z ∧ ∀x.(qF x ⊃ x' ≠ z))  ∧ ∀x.(qF x ⊃ qF x') ⊃ ∀x.(integer x ⊃ qF x)%1
 
On the domain of non-negative integers, we might put %2qF↑h(x) ≡ x ≥ h%1,
and this would show that there are no integers at all.  Well, it's a
counterexample to something.
 
Blocks world formulas:
 
%2isblock A ∧ isblock B ∧ isblock C%1
 
circumscribes to
 
%2qF A ∧ qF B ∧ qF C ⊃ ∀x.(isblock x ⊃ qF x)%1,
 
which tells us that ⊗A, ⊗B and ⊗C are the only blocks.  This is obtained

by setting %2qF x ≡ (x = A ∨ x = B ∨ x = C)%1.
 
Suppose that we also have the formula
 
%2on(A,B) ∧ on(B,C)%1.
 
Then circumscribing this formula with respect to ⊗on  will yield
 
%2qF(A,B) ∧ qF(B,C) ⊃ ∀x y.(on(x,y) ⊃ qF(x,y))%1,
 
and substituting  %2qF(x,y) = (x = A ∧ y = B ∨ x = B ∧ y = C)%1 yields
the conclusion that ⊗on(A,B) and ⊗on(B,C) are the only ⊗on  relations.
 
	Now suppose that we want to say that every block that isn't on another
block is on the table which isn't counted as a block.
We have
 
%2¬isblock Table%1
 
and
 
%2∀x y.(on(x,y) ⊃ isblock x ∧ (isblock y ∨ y = Table))%1.
EPISTEMOLOGICAL PROBLEMS OF ARTIFICIAL INTELLIGENCE
 
by John McCarthy
 
	(McCarthy 1959) proposes a program with common sense
that would represent what it knows mainly by sentences
in a suitable logical language.  It would decide what to do by
deducing a conclusion that it should perform a certain act.
Peforming the act would create a new situation, and it
would again decide what to do.  This requires
representing both knowledge about the particular situation
and general common sense knowledge as sentences of logic.

	%A problem, which we later called the "qualification problem",
immediately arose in connection with the representation of
general common sense knowledge.  It seemed that in order to
represent the conditions for the successful performance of
an action, an infinite amount of detail would have to be
present.  For example, the successful use of a boat to cross
a river requires, if the boat is a rowboat, that the oars
and rowlocks be present and unbroken, and that they fit each other.

	Many other necessary conditions can be added, making the rules
for using a rowboat almost impossible to apply, and yet anyone
will still be able to think of additional requirements not
yet stated.   Circumscription is a candidate for a solution
of this "qualification problem".

	Circumscription is a rule of conjecture for "jumping to
the conclusion" that the objects that can be shown to have
a certain property by reasoning from certain
facts are all the objects that have this property.
More generally, circumscription can be used to conjecture that
the tuples of objects that can be shown to be related in a
certain way are all the tuples satisfying this relation.
Thus we can postulate that a boat can be used to cross
a river unless "something" prevents it.
Then circumscription may be used to conjecture that the
only entities that can prevent the use of the boat are
those whose existence follows from the facts at hand.
If no lack of oars or other circumstance preventing boat use is deducible,
then the boat is concluded to be usable.
The correctness of this conclusion depends on our having
"taken into account" all relevant facts when we made the circumscription.

	Circumscription formalizes several processes of human informal reasoning.
For example, common sense reasoning is ordinarily ready to jump to the
conclusion that a tool can be used for its intended purpose unless
something prevents its use.  Considered purely extensionally, such
a statement conveys no information; it seems merely to assert that
a tool can be used for its intended purpose unless it can't.
Heuristically, the statement is not just a
tautologous disjunction; it suggests forming a plan to use the tool.



	(McCarthy 1959) proposed a program with "common sense" that
would express its knowledge about the world in general and about
the particular problem in a suitable logical language.  It would then
reason in this language attempting to derive a sentence of the form
%2I should do X%1 after which it would do ⊗X.  This approach was further
developed in (McCarthy 1963) and (McCarthy and Hayes 1969), but by
1969 it was already clear that something more than deduction is necessary
in order to express and use common sense knowledge.  Further analysis
showed that what was missing was the ability to jump to the conclusion
that the entities taken into account are all that are relevant to the
problem.


.if false then begin
	%2Circumscription induction%1 is a formalized %2rule of conjecture%1
that can be used along with the %2rules of inference%1 of first order logic.
A computer program can use circumscription induction to conjecture that 
the known entities of a given kind are all there are.
.end
Heuristics of Circumscription
 
The definition of circumscription as a rule of conjecture and the above
examples of its use to make conjectures useful in the blocks world
and the missionaries and cannibals problem don't tell us how a
heuristic program should use circumscription in general.  Here are some
considerations.
 
1. Given a certain class of sentences, a program has a choice of many
circumscriptions, since it can take any subcollection of the sentences and any
predicate symbol.  Moreover, it can retrieve further sentences from
its long term memory before doing the circumscription.
 
2. Having done the circumscription, the program has to choose what predicate
expression to substitute for the qF.  Then it has its usual choices
of what deductions to make.
 
3. We can envisage these choices as being built into the structure of
the program or as being determined by further reasoning.  In the
latter case, there must be a formalized metalanguage in which heuristic
information about what circumscriptions are appropriate in given circumstances can
be expressed.  Ideally, the language and the metalanguage should
be the same - as is the case with natural languages.